package com.gaogzhen.algorithm.leetCode;

import java.util.*;

/**
 * 1512. 好数对的数目
 */
public class NumIdenticalPairs {
    public static void main(String[] args) {
        int[] a = {1, 2, 1, 1};
        System.out.println(numIdenticalPairs2(a));
    }

    // 双层循环
    public static int numIdenticalPairs(int[] nums) {
        int len = nums.length, count = 0;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (nums[j] == nums[i])
                    count++;
            }
        }
        return count;
    }

    // 先排序在统计
    public static int numIdenticalPairs1(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int count = 0, i = 0;
        while(i < len) {
            int j = i + 1;
            while (j < len && nums[j] == nums[i]) {
                j++;
            }
            if (j - 1 != i)
                count += (j - i) * (j - i - 1) / 2;
            i = j;
        }
        return count;
    }

    // 利用map计数
    public static int numIdenticalPairs2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num: nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            }else {
                map.put(num, 1);
            }
        }
        int count = 0;
        Collection<Integer> values = map.values();
        for (int num: values) {
            count += num * (num - 1)/2;
        }
        return count;
    }

    public static int numIdenticalPairs3(int[] nums) {
        //计数数组，之所以长为101是为了让count[100]不越界
        //java中数组中的数字会被初始化为0， 即count[i] 目前均为0
        int[] count = new int[nums.length + 1];
        //待输出的最终结果
        int oucome = 0;
        //nums数组中的数字个数
        int length = nums.length;
        //遍历
        for(int i = 0; i < length; i++)
        {
            //temp即为当前数字
            int temp = nums[i];

            //关键点！  原因见下文
            oucome += count[temp];

            //数字nums[i]出现一次，则计数数组count对应加一
            count[temp] += 1;
        }
        return oucome;
    }

}
